package DynamicProgramming.Medium;

public class LC0790 {
    /**
     * 官方解法。dp[i,s]表示铺到第i列时，如果呈现状态s，那么最多有多少种铺法。0表示第i列为空，3表示第i列为满，
     * 1和2表示第i列的上面一个或下面一个方形为满。
     */
    public int numTilings(int n) {
        int[][] dp = new int[n + 1][4];
        int MOD = 1000000007;
        dp[1][3] = 1;
        dp[1][0] = 1;
        dp[1][1] = dp[1][2] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][3]; // 不能由dp[i-2]或更早的状态转换而来：它们是dp[i-1]的子问题。
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][0]) % MOD;
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][0]) % MOD;
            dp[i][3] = (((dp[i - 1][3] + dp[i - 1][0]) % MOD + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD;
        }

        return dp[n][3];
    }
}
